原点|直径_[JavaScript刷题]排序最接近原点的K个点,leetcode973

篇首语：本文由编程笔记#小编为大家整理，主要介绍了[Javascript 刷题] 排序 - 最接近原点的 K 个点, leetcode 973相关的知识，希望对你有一定的参考价值。

github repo 地址: https://github.com/GoldenaArcher/js_leetcode&＃xff0c;Github 的目录 大概 会更新的更勤快一些。

题目地址&＃xff1a;973. K Closest Points to Origin

题目

如下&＃xff1a;

Given an array of points where points[i] &＃61; [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 &＃43; (y1 - y2)2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

解题思路

其实就是 kth elements 的变种&＃xff0c;用 堆排序(priority queue, 用 PQ 实现一个 max heap)、快速排序 都能比较好的解决问题。

主要麻烦的地方就在于&＃xff0c;Javascript 内部是没有实现 Priority Queue 的&＃xff0c;所以根据需求可能需要手写一个 PQ&＃xff0c;如果是 OA 这种情况会稍微尴尬一些&＃xff0c;如果不是 OA 的话&＃xff0c;问面试官是不是可以模拟一个 PQ 也可以。

这里使用的方法是新建一个长度为 K 的 PQ&＃xff0c;如果新发现的点直径小于当前 heap 中的最大值时&＃xff0c;将当前的点压入 heap 中。

以网上随便找了个图为例&＃xff1a;

这个 max heap 中的最大值为 100&＃xff0c;现在如果碰上了一个与原点距离只有 90 的点&＃xff0c;&＃xff0c;那么就需要移除最大值&＃xff0c;将 90 压进 max heap 中&＃xff0c;剩下的排序操作&＃xff0c;让 PQ 去完成即可。

使用 Javascript 解题

// mimic a max heap
const maxHeap &＃61; (arr) &＃61;>
arr.sort((a, b) &＃61;> b[0] - a[0]);
;
const getArea &＃61; (loc) &＃61;>
const [x, y] &＃61; loc;
// omit Mqth.sqrt() here
return x * x &＃43; y * y;
;
/**
* &＃64;param number[][] points
* &＃64;param number k
* &＃64;return number[][]
*/
var kClosest &＃61; function (points, k)
const pq &＃61; [];
for (let i &＃61; 0; i < points.length; i&＃43;&＃43;)
const area &＃61; getArea(points[i]);
if (pq.length < k)
pq.push([area, points[i]]);
continue;

maxHeap(pq);
if (area <&＃61; pq[0][0])
pq.shift();
pq.push([area, points[i]]);


return pq.reduce((accu, res) &＃61;>
accu.push(res[1]);
return accu;
, []);
;